/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 * 二叉树的前序遍历
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月17日
 */
public class BinaryTreePreorderTraversal {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null) {
            return result;
        }
        preOrderTraversal(root, result);
        return result;
    }

    /**
     * 前序遍历
     * @param root
     * @param result
     * @author towan 2015年5月21日
     */
    private void preOrderTraversal(TreeNode root, List<Integer> result) {
        if (root != null) {
            result.add(root.val);
            preOrderTraversal(root.left, result);
            preOrderTraversal(root.right, result);
        }
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(3);
        TreeNode tleft = new TreeNode(8);
        TreeNode tright = new TreeNode(7);
        t1.left = tleft;
        t1.right = tright;

        tright.left = new TreeNode(3);
        tright.right = new TreeNode(8);

        tleft.left = new TreeNode(9);
        tleft.right = new TreeNode(2);

        BinaryTreePreorderTraversal traversal = new BinaryTreePreorderTraversal();
        List<Integer> list = traversal.preorderTraversal(t1);
        System.out.println(list);
    }
}
